<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 
            示例 1:

            输入: amount = 5, coins = [1, 2, 5]
            输出: 4
            解释: 有四种方式可以凑成总金额:

            5=5
            5=2+2+1
            5=2+1+1+1
            5=1+1+1+1+1
            示例 2:

            输入: amount = 3, coins = [2]
            输出: 0
            解释: 只用面额2的硬币不能凑成总金额3。
            示例 3:

            输入: amount = 10, coins = [10]
            输出: 1
            注意，你可以假设：

            0 <= amount (总金额) <= 5000
            1 <= coin (硬币面额) <= 5000
            硬币种类不超过 500 种
            结果符合 32 位符号整数

        */


        /*
            考虑这道题用回溯算法来做可以吗？
            1. 从index=0开始去计算，能不能凑成目标数，关键是能不能被整除吧，如果不能，就无法单独凑出，
                1.1 如果能够整除，比如3元硬币，凑成目标15，15 / 3 = 5 , 此时3 * 5是一定能够凑成目标数的
                1.2 此外，要看15 - 3的值后，是12，12能否和其他硬币凑出来呢？如果能，比如有1，就是12 + 3 * 1就是15，组合数又加了一个
        */
        var change = function(amount, coins) {
            // 需要传递哪些参数
            let count = 0
            const backtrack = (remain, startIndex) => {
                // 找到一种组合
                if (remain === 0) return count += 1
                // 剪枝 
                if (remain < 0 || startIndex >= coins.length) {
                    return
                }
                // 从startIndex开始遍历所有硬币
                for (let i = startIndex; i < coins.length; i++) {
                    backtrack(remain - coins[i], i)
                }
            }
            backtrack(amount, 0)
            return count
        };
        console.log(change(5, [1, 2, 5]));
    </script>
</body>

</html>